/*
Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
Author : nflush@outlook.com
Date   : 2016-07-11
*/

/*
123. Best Time to Buy and Sell Stock III

    Total Accepted: 61227
    Total Submissions: 227417
    Difficulty: Hard

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Subscribe to see which companies asked this question
*/
class Solution {
    typedef struct {
        int diff;
        int bot;
    }PDIFF;
private:
    int maxDiff(PDIFF ad[2], int bott, int top){
        
    }
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1) return 0;
        PDIFF ad[2] = {0};
        int last = prices[0];
        int minPrice = prices[0];
        int sum = 0;
        for (int i = 1; i < prices.size(); i++){
            if (prices[i] < last){
                last = prices[i];
            } else {
                sum += prices[i] - last;
            }
        }
        return sum;
    }
};
